//
// Created by 郑楚彬 on 2018/4/2.
//
#include <iostream>
#include <stdio.h>
#include <stdlib.h>

#define Max 100

/**
 * 顺序栈定义
 */
typedef struct SqStack{
    int data[Max];  // 存放栈中元素
    int top;        // 栈顶指针
};

/**
 * 初始化栈
 *
 * @param st
 */
void initStack(SqStack &st){
    // 栈空状态
    st.top = -1;
}

/**
 * 判断栈空
 * @param st
 * @return
 */
int isStackEmpty(SqStack &st){
    if(st.top == -1){
        return 1;
    }else{
        return 0;
    }
}

/**
 * 判断栈满
 * @param st
 * @return
 */
int isStackFull(SqStack &st){
    if(st.top == Max-1){
        return 1;
    }else{
        return 0;
    }
}

/**
 * 进栈算法
 *
 * @param st
 * @param x
 * @return
 */
int pushStack(SqStack &st, int x){
    //这里要注意，栈满不能进栈。
    if(st.top == Max-1){
        return 0;
    }
    //先移动指针，再进栈
    st.top ++;
    st.data[st.top] = x;
    return 1;
}

/**
 * 出栈算法
 *
 * @param st
 * @param x
 * @return
 */
int popStack(SqStack &st, int &x){
    //注意，如果栈空则不能出栈
    if(st.top == -1){
        return 0;
    }
    //先取出元素，再移动指针
    x = st.data[st.top];
    st.top--;
    return 1;
}

/*============================= 真题仿造 =============================*/
/**
    2. 请利用两个栈 S1 和 S2 来模拟一个队列，假设栈中元素为 int 型，栈中元素最多为 MAX。
       已知栈的三个运算定义如下:
            PUSH(ST,x):元素 x 入 ST 栈;
            POP(ST,&x):ST 栈顶元素出栈，赋给变量 x;
            Sempty(ST):判 ST 栈是否为空。
       如何利用栈的运算来实现该队列的三个运算:
            enqueue:元素入队列;
            dequeue:元素出队列;
            queue_empty:判断队列是否为空，空返回 1 不，空返回 0。
    要求: (1)给出基本设计思想。
         (2)根据设计思想，采用 C 或 C++语言描述算法，关键之处给出注释。
 */

/**
    3. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头 指针，
       请写出相应的入队列和出队列算法。
 */
void enQueue(LNode *&rear, int &x){
    LNode *p = (LNode *) malloc(sizeof(LNode *));
    p->data = x;
    p->next = rear->next;
    rear->next = p;
    rear = p;
}

int deQueue(LNode *&rear, int &x){
    // 队列为空
    if(rear->next = rear)
        return 0;
    // 待删除节点
    LNode *first = rear->next->next;
    rear->next->next = first->next;
    x = first->data;

    //如果元素出队后队列为空需要特殊处理
    if(first == rear){
        rear = rear->next;
    }
    free(first);
    return 1;
}

/**
 *  4. 如果允许在循环队列的两端都可以进行插入和删除操作。要求:
 *   (1) 写出循环队列的类型定义;
 *   (2) 写出“从队尾删除”和“从队头插入”的算法。
 */
typedef struct deque{
    int data[MAX];
    int front;
    int rear;
}deque;


/*
 *  算法实现“从队头插入”元素 x。
 */
int enCycQueue(deque &cyc, int x){
    // 判断队满
    if(cyc.rear == (cyc.front-1+MAX) % MAX){
        return 0;
    }
    cyc.data[cyc.front] = x;
    cyc.front = (cyc.front-1+MAX) % MAX;
    return 1;
}

/*
 * 算法实现“从队尾删除”，若删除成功用 x 接纳删除元素，返回 1，否则返回 0。
 */
int deQueue(deque &cyc, int &x){
    // 判断队空
    if(cyc.front == cyc.rear){
        return 0;
    }
    x = cyc.data[cyc.rear];
    cyc.rear = (cyc.rear-1+MAX) % MAX;
    return 1;
}


/**
 * 中缀表达式转成后缀表达式
 */

/**
 * 求操作符的优先级
 * @param c     操作符
 * @param flag  1: 在栈中， 0: 不在栈中
 * @return
 */
int getPrecedence(char c, int flag){
    switch(c){
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
        case '(':
            // 左括号比较特殊，在栈外优先级高，在栈顶优先级低
            if(flag==0){
                return 3;
            }else{
                return 0;
            }
        default:
            printf("ERROR: Invalid character.");
            return -1;
    }
}

/**
 * 判断是否为操作符
 * @param c
 * @return
 */
int isOperator(char c){
    if(c=='+' || c=='-' || c=='*' || c=='/' || c=='(' || c==')'){
        return 1;
    }else{
        return 0;
    }
}

char* infix2Postfix(char *ch){
    // 输出栈
    char output[Max];
    int outputTop = -1;

    // 操作符栈
    char operators[Max];
    int top = -1;

    char c;
    while((c=*ch) != '\0'){
        // 操作数，直接输出
        if(!isOperator(c)){
            output[++outputTop] = c;
            ch++;
        // 操作符
        }else{
            // 栈为空，遇到运算符，入栈
            if(top == -1){
                operators[++top] = c;
                ch++;
            } else{
                if(c == ')'){
                    // ﻿遇到右括号，执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出
                    while(top!=-1 && operators[top]!='('){
                        output[++outputTop] = operators[top--];
                    }
                    // '(' 出栈，但不输出
                    operators[top--];
                    ch++;
                } else{
                    char outPrecedence = getPrecedence(c, 0);
                    // ﻿栈不为空，并且栈顶元素大于或等于该运算符则弹出
                    while(top!=-1 && getPrecedence(operators[top], 1) >= outPrecedence){
                        output[++outputTop] = operators[top--];
                    }
                    operators[++top] = c;
                    ch++;
                }
            }
        }
    }
    // 将栈中剩余的元素弹出
    while(top!=-1){
        output[++outputTop] = operators[top--];
    }
    output[++outputTop] = '\0';
    return output;
}
